#include <vector>
/*
void Quick_sort(vector<int> &nums,int begin,int end){
    if (begin >= end)
		return;
    int l = begin,r = end,first = nums[begin];
    while(l < r){
        while(l < r && nums[r] >= first){
            r--;
        }
        while(l < r && nums[l] <= first){
            l++;
        }
        if(l < r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
        }
    }
    nums[begin] = nums[l];
    nums[l] = first;
    Quick_sort(nums,begin,l-1);
    Quick_sort(nums,l+1,end);
}
*/


//快速排序，平均时间复杂度O(nlog(n)),空间复杂度O(log(n)),不稳定
void Quick_sort(vector<int> &nums,int begin,int end){
    if(begin >= end)
        return;
    int l = begin,r = end,first = nums[begin];
    while(l < r){
        while(l < r && nums[r] >= first){
            r--;
        }
        nums[l] = nums[r];
        while(l < r && nums[l] <= first){
            l++;
        }
        nums[r] = nums[l];
    }
    nums[l] = first;
    Quick_sort(nums,begin,l-1);
    Quick_sort(nums,l+1,end);
}